import java.util.ArrayList;
import java.util.List;

class Solution2 {
    public static void main(String[] args) {
         List<Integer> A = new ArrayList<>();
        List<Integer> B = new ArrayList<>();
        List<Integer> C = new ArrayList<>();
        A.add(1) ;
        A.add(2) ;
        hanota(A , B , C);
        System.out.println(C);
    }
    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
          move(A.size() , A , B , C) ;
    }
    private static void move(int size , List<Integer> A, List<Integer> B, List<Integer> C ){
        if(size == 1){
            C.add(A.indexOf(0));
            A.remove(0) ; 
            return ;
        }
        move(size-1 , A , C , B) ;
        C.add(A.indexOf(0));
        A.remove(0);
        move(size-1 , B , A , C) ;
        
    }


}
class Solution3 {
    public double myPow(double x, int n) {
        return n>=0 ? pow(x,(long)n) : 1.0 / pow(x, (long)n);
    }
    private double pow(double x , long n){
        if(n == 0){
            return 1.0 ;
        }
        double sum = pow(x , n/2) ;
        return n%2==0 ? sum*sum : sum*sum*x ;
    }
}
class Solution4 {
    public int climbStairs(int n) {
        if(n == 1) return 1 ;
        if(n==2) return 2 ;
        int[] dp = new int[n+1] ;
        dp[0] = 1 ;
        dp[1] = 1 ;
        for(int i=2 ; i <= n ; i ++){
            dp[i] = dp[i-1]+dp[i-2] ;
        }
        ;
        return dp[n] ;
    }
}
class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size() , A , B , C) ;
    }
    private void move(int size , List<Integer> A, List<Integer> B, List<Integer> C ){
        if(size == 1){
            C.add(A.remove(A.size()-1));
            return ;
        }
        move(size-1 , A , C , B) ;
        C.add(A.remove(A.size()-1)) ;
        move(size-1 , B , A , C) ;

    }
}
